#include <iostream>
#define ls (rt << 1)
#define rs (rt << 1 | 1)
using namespace std;
const int N = 500010;
int n, m, w[N];
int L[N], R[N], sum[N], lmax[N], rmax[N], tmax[N];
void pushup(int rt, int l, int r) {
  sum[rt] = sum[l] + sum[r];
  lmax[rt] = max(lmax[l], sum[l] + lmax[r]);
  rmax[rt] = max(rmax[l] + sum[r], rmax[r]);
  tmax[rt] = max(rmax[l] + lmax[r], max(tmax[l], tmax[r]));
}
void build(int rt, int l, int r) {
  L[rt] = l;
  R[rt] = r;
  if (l == r) {
    sum[rt] = lmax[rt] = rmax[rt] = tmax[rt] = w[r];
  } else {
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(rt, ls, rs);
  }
}
void modify(int rt, int idx, int val) {
  if (L[rt] == R[rt]) {
    sum[rt] = lmax[rt] = rmax[rt] = tmax[rt] = val;
  } else {
    int mid = L[rt] + R[rt] >> 1;
    if (idx <= mid)
      modify(ls, idx, val);
    else
      modify(rs, idx, val);
    pushup(rt, ls, rs);
  }
}
int query(int rt, int l, int r) {
  if (l <= L[rt] && R[rt] <= r)
    return rt;
  else {
    int mid = L[rt] + R[rt] >> 1;
    if (r <= mid)
      return query(ls, l, r);
    else if (l > mid)
      return query(rs, l, r);
    else {
      int left = query(ls, l, r);
      int right = query(rs, l, r);
      tmax[++n] = max(rmax[left] + lmax[right], max(tmax[left], tmax[right]));
      return n;
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> w[i];
  build(1, 1, n);
  while (m--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) {
      if (x > y) swap(x, y);
      cout << tmax[query(1, x, y)] << endl;
    } else {
      modify(1, x, y);
    }
  }
}
